
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1165. -- [Baltic2008]Gates -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1165: [Baltic2008]Gates</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>162 MB<br><span class=green>Submit: </span>0&nbsp;&nbsp;<span class=green>Solved: </span>0<br>[<a href='submitpage.php?id=1165'>Submit</a>][<a href='problemstatus.php?id=1165'>Status</a>][<a href='bbs.php?id=1165'>Discuss</a>]</center><h2>Description</h2><div class=content><div style="text-indent: 21pt">厌倦了你的工作<span>, 你从IT行业跳槽到了一家水产养殖公司.</span></div>
<div style="text-indent: 21pt">你的第一项任务是把两个水槽分隔开<span>. 尝试了操作手册的内容并仔细观察之后, 你了解了水槽的工作机制.</span></div>
<div style="text-indent: 21pt">两个水槽由<span>n条通道相连, 每个通道上有两个水闸. 只有两个水闸都打开时通道才开启, 其余情况下通道都是封闭的.</span></div>
<div style="text-indent: 21pt">这<span>2n个水闸的状态由开关控制. 每个水闸的状态恰好由一个开关控制, 当然某个开关可能控制多个水闸或者不控制任何水闸. 一条通道上的两个水闸也有可能由同一个开关控制.</span></div>
<div style="text-indent: 21pt">开关一共有<span>m个, 编号为1; 2;&hellip;&hellip;;m, 每个开关有两种状态: 开和关. 而水闸受开关控制的方式有两种:</span></div>
<div style="margin: 0cm 0cm 0pt 42pt; text-indent: -21pt"><span>l<span style="font: 7pt 'Times New Roman'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span>开关开时水闸打开<span>, 开关关时水闸关闭.</span></div>
<div style="margin: 0cm 0cm 0pt 42pt; text-indent: -21pt"><span>l<span style="font: 7pt 'Times New Roman'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span>开关关时水闸打开<span>, 开关开时水闸关闭.</span></div>
<p><img height="454" alt="" width="301" src="/JudgeOnline/upload/201108/11(3).jpg" /></p></div><h2>Input</h2><div class=content><p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0"><span style="font-family: 宋体"><font size="3">输入的第一行包含两个整数<span lang="EN-US">n</span>和<span lang="EN-US">m.<o:p></o:p></span></font></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0"><span style="font-family: 宋体"><font size="3">接下来<span lang="EN-US">n</span>行每行包含了一条通道的信息<span lang="EN-US">, </span>由四个整数<span lang="EN-US">a; S a; b; S b</span>表示<span lang="EN-US">. a</span>和<span lang="EN-US">b</span>表示控制两个水闸的开关编号<span lang="EN-US">,</span>而<span lang="EN-US">S a</span>和<span lang="EN-US">S b</span>为<span lang="EN-US">0</span>或<span lang="EN-US">1, </span>表示水闸受开关控制的方式<span lang="EN-US">. S i = 0</span>表示开关<span lang="EN-US">i</span>关时水闸关<span lang="EN-US">, </span>以此类推<span lang="EN-US">.<o:p></o:p></span></font></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span lang="EN-US" style="font-family: 宋体"><o:p><font size="3">&nbsp;</font></o:p></span></p>
<p></p></div><h2>Output</h2><div class=content><p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0"><span style="font-family: 宋体"><font size="3">如果存在一种开关的状态使得所有通道都封闭<span lang="EN-US">, </span>则输出<span lang="EN-US">m</span>行<span lang="EN-US">, </span>每行一个整数<span lang="EN-US">0</span>或<span lang="EN-US">1. </span>第<span lang="EN-US">i</span>行为<span lang="EN-US">0</span>表示编号为<span lang="EN-US">i</span>的开关应当关<span lang="EN-US">, </span>为<span lang="EN-US">1</span>则表示开关应当开<span lang="EN-US">.</span></font></span></p>
<p><span style="font-family: 宋体"><span lang="EN-US"><o:p></o:p></span></span>
<p></p>
</p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0"><span style="font-family: 宋体"><font size="3">如果不存在这样的状态<span lang="EN-US">, </span>输出一行<span lang="EN-US">&ldquo;IMPOSSIBLE&rdquo;.<o:p></o:p></span></font></span></p></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>3 2<br />
1 0 2 1<br />
1 0 2 0<br />
1 1 2 1<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>0<br />
1<br />
</span></div><h2>HINT</h2>
			<div class=content><p><p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-family: 宋体"><font size="3">对所有数据<span lang="EN-US">, n &lt;= 250000;m &lt;= 500000.</span></font></span></p><br />
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-family: 宋体"><font size="3"><span lang="EN-US"><o:p></o:p></span></font></span></p><br />
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-family: 宋体"><font size="3"><span lang="EN-US">需要SJ，请不要提交！</span></font></span></p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=1165'>Submit</a>][<a href='problemstatus.php?id=1165'>Status</a>][<a href='bbs.php?id=1165'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
